package leetcode_BFS;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 腐烂的橘子
 * <p>算法: 多源 BFS</p>
 * @author yezh
 * @date 2023/8/14 14:51
 */
public class _994 {

    public int orangesRotting(int[][] grid) {
        // 多源 BFS, 即起始点有多个
        int ans = 0, fresh = 0, m = grid.length, n = grid[0].length;
        Deque<int[]> queue = new ArrayDeque<>();
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) ++fresh;
                else if (grid[i][j] == 2) queue.offer(new int[]{i, j});
            }
        while (fresh > 0 && !queue.isEmpty()) {
            int len = queue.size();
            ++ans;
            while (len-- > 0) {
                int[] poll = queue.poll();
                if (poll[0] + 1 < m && grid[poll[0] + 1][poll[1]] == 1) {
                    grid[poll[0] + 1][poll[1]] = 2;
                    --fresh;
                    queue.offer(new int[]{poll[0] + 1, poll[1]});
                }
                if (poll[0] - 1 >= 0 && grid[poll[0] - 1][poll[1]] == 1) {
                    grid[poll[0] - 1][poll[1]] = 2;
                    --fresh;
                    queue.offer(new int[]{poll[0] - 1, poll[1]});
                }
                if (poll[1] + 1 < n && grid[poll[0]][poll[1] + 1] == 1) {
                    grid[poll[0]][poll[1] + 1] = 2;
                    --fresh;
                    queue.offer(new int[]{poll[0], poll[1] + 1});
                }
                if (poll[1] - 1 >= 0 && grid[poll[0]][poll[1] - 1] == 1) {
                    grid[poll[0]][poll[1] - 1] = 2;
                    --fresh;
                    queue.offer(new int[]{poll[0], poll[1] - 1});
                }
            }
        }
        return fresh == 0 ? ans : -1;
    }

}
